home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / VELENG10.ZIP / ADJMTRX.C next >
Encoding:
C/C++ Source or Header  |  1997-07-27  |  8.0 KB  |  312 lines
  1. // ****************************************************************************
  2. // *                                                                          *
  3. // *                      Velena Source Code V1.0                             *
  4. // *                   Written by Giuliano Bertoletti                         *
  5. // *       Based on the knowledged approach of Louis Victor Allis             *
  6. // *   Copyright (C) 1996-97 by Giuliano Bertoletti & GBE 32241 Software PR   *
  7. // *                                                                          *
  8. // ****************************************************************************
  9.  
  10. // Portable engine version.
  11. // read the README file for further informations.
  12.  
  13. // ==========================================================================
  14.  
  15. #include <stdio.h>
  16. #include <string.h>
  17. #include <stdlib.h>
  18. #include <malloc.h>
  19.  
  20. #include "connect4.h"
  21. #include "con4vals.h"
  22.  
  23. #include "rules.h"
  24. #include "pnsearch.h"
  25. #include "proto.h"
  26.  
  27. extern char *rulename[];
  28.  
  29. short rulecombo[9][9]={ 1, 1, 1, 1, 3, 3, 1, 1, 1,
  30.                         1, 1, 1, 1, 1, 1, 1, 1, 1,
  31.                         1, 1, 1, 1, 1, 1, 1, 1, 1,
  32.                         1, 1, 1, 4, 3, 3, 1, 4,12,
  33.                         3, 1, 1, 3, 8, 8, 3, 6, 6,
  34.                         3, 1, 1, 3, 8, 8, 3, 3, 3,
  35.                         1, 1, 1, 1, 3, 3, 1, 1, 1,
  36.                         1, 1, 1, 4, 6, 3, 1, 4, 4,
  37.                         1, 1, 1,12, 6, 3, 1, 4, 4 };
  38.  
  39. char **allocate_matrix(struct board *board)
  40.     {
  41.     unsigned char **matrix;
  42.     short x;
  43.  
  44.     matrix=(unsigned char **)malloc(board->sp * sizeof(unsigned char *));
  45.     if(!matrix) fatal_error("Memory overflow!");
  46.  
  47.     for(x=0;x<board->sp;x++)
  48.         {
  49.         matrix[x]=(unsigned char *)malloc(x+1);
  50.         if(!matrix[x]) fatal_error("Cannot allocate adjacency matrix");
  51.         }
  52.  
  53.     return (char **)matrix;
  54.     }
  55.  
  56. void free_matrix(char **matrix,struct board *board)
  57.     {
  58.     short x;
  59.  
  60.     for(x=0;x<board->sp;x++)
  61.         free(matrix[x]);
  62.  
  63.     free(matrix);
  64.     }
  65.  
  66. short overlap(struct board *board,short p1,short p2)
  67.     {
  68.     short x,y;
  69.     short temp[(BOARDX+1)*(BOARDY+2)];
  70.  
  71.     for(x=0;x<board->solution[p1]->sqinvnumb;x++)
  72.         temp[board->solution[p1]->sqinv[x]]=NO;
  73.  
  74.     for(x=0;x<board->solution[p2]->sqinvnumb;x++)
  75.         temp[board->solution[p2]->sqinv[x]]=YES;
  76.  
  77.     for(x=0;x<board->solution[p1]->sqinvnumb;x++)
  78.         if(temp[board->solution[p1]->sqinv[x]]) return YES;
  79.  
  80.     return NO;
  81.     }
  82.  
  83. short claimeven_below(struct board *board,short p1,short p2)
  84.     {
  85.     short x,y,name,q1,q2;
  86.     short q1x,q2x,q1y,q2y,solcheck;
  87.  
  88.     name=board->solution[p1]->solname;
  89.     if(name!=HIGHINVERSE && name!=LOWINVERSE)
  90.         {
  91.         q1=p2;
  92.         q2=p1;
  93.         }
  94.     else
  95.         {
  96.         q1=p1;
  97.         q2=p2;
  98.         }
  99.  
  100.     name=board->solution[q1]->solname;
  101.     if(name!=HIGHINVERSE && name!=LOWINVERSE)
  102.         fatal_error("Condition not coming from an Inverse");
  103.  
  104.     if(board->solution[q2]->solname==AFTEREVEN)
  105.         {
  106.         solcheck=board->solution[q2]->sqinvnumb/2;
  107.  
  108.         for(x=0;x<2;x++)
  109.             {
  110.             /* That's tricky to get the lowest square in the column */
  111.             q1x=ELX(board->solution[q1]->sqinv[x+2]);
  112.             q1y=ELY(board->solution[q1]->sqinv[x+2]);
  113.  
  114.             for(y=0;y<solcheck;y++)
  115.                 {
  116.                 q2x=ELX(board->solution[q2]->sqinv[solcheck+y]);
  117.                 q2y=ELY(board->solution[q2]->sqinv[solcheck+y]);
  118.  
  119.                 if(q1x==q2x && q1y>q2y && (q2y&1)==1) return YES;
  120.                 }
  121.             }
  122.         }
  123.     else if (board->solution[q2]->solname==BEFORE ||
  124.         board->solution[q2]->solname==SPECIALBEFORE)
  125.             {
  126.             solcheck=board->solution[q2]->sqinvnumb/2;
  127.  
  128.             for(x=0;x<2;x++)
  129.                 {
  130.                 /* That's tricky to get the lowest square in the column */
  131.                 q1x=ELX(board->solution[q1]->sqinv[x+2]);
  132.                 q1y=ELY(board->solution[q1]->sqinv[x+2]);
  133.  
  134.                 for(y=0;y<solcheck;y++)
  135.                     {
  136.                     q2x=ELX(board->solution[q2]->sqinv[1+(y<<1)]);
  137.                     q2y=ELY(board->solution[q2]->sqinv[1+(y<<1)]);
  138.  
  139.                     if(q1x==q2x && q1y>q2y && (q2y&1)==1) return YES;
  140.                     }
  141.                 }
  142.             }
  143.  
  144.     else if(board->solution[q2]->solname==CLAIMEVEN)
  145.         {
  146.         for(x=0;x<2;x++)
  147.             {
  148.             /* That's tricky to get the lowest square in the column */
  149.             q1x=ELX(board->solution[q1]->sqinv[x+2]);
  150.             q1y=ELY(board->solution[q1]->sqinv[x+2]);
  151.             q2x=ELX(board->solution[q2]->sqinv[0]);
  152.             q2y=ELY(board->solution[q2]->sqinv[0]);
  153.  
  154.             if(q1x==q2x && q1y>q2y) return YES;
  155.             }
  156.         }
  157.     else if(board->solution[q2]->solname==BASECLAIM)
  158.         {
  159.         for(x=0;x<2;x++)
  160.             {
  161.             /* That's tricky to get the lowest square in the column */
  162.             q1x=ELX(board->solution[q1]->sqinv[x+2]);
  163.             q1y=ELY(board->solution[q1]->sqinv[x+2]);
  164.             q2x=ELX(board->solution[q2]->sqinv[3]);
  165.             q2y=ELY(board->solution[q2]->sqinv[3]);
  166.  
  167.             if(q1x==q2x && q1y>q2y) return YES;
  168.             }
  169.         }
  170.  
  171.     else fatal_error("Could not figure out what combination I am dealing about");
  172.  
  173.     return NO;
  174.     }
  175.  
  176. short column_wdoe(struct board *board,short p1,short p2)
  177.     {
  178.     char debug[80];
  179.     short joinmtrx[(BOARDX+1)*(BOARDY+2)];
  180.     short x,y,cnt,answer=YES,w1,w2;
  181.  
  182.     w1=board->solution[p1]->solname;
  183.     w2=board->solution[p2]->solname;
  184.  
  185.     if(w1!=SPECIALBEFORE && w1!=BEFORE && w1!=AFTEREVEN && w1!=LOWINVERSE)
  186.         {
  187.         sprintf(debug,"Inconsistent wdow p1: rule = %d",w1);
  188.         fatal_error(debug);
  189.         }
  190.  
  191.     if(w2!=SPECIALBEFORE && w2!=BEFORE && w2!=AFTEREVEN && w2!=LOWINVERSE)
  192.         {
  193.         sprintf(debug,"Inconsistent wdow p2: rule = %d",w2);
  194.         fatal_error(debug);
  195.         }
  196.  
  197.     memset(joinmtrx,0,(BOARDX+1)*(BOARDY+2)*sizeof(short));
  198.  
  199.     for(x=0;x<board->solution[p1]->sqinvnumb;x++)
  200.         joinmtrx[board->solution[p1]->sqinv[x]]=YES;
  201.  
  202.     for(y=0;y<board->solution[p2]->sqinvnumb;y++)
  203.         joinmtrx[board->solution[p2]->sqinv[y]]=YES;
  204.  
  205.     for(x=0;x<BOARDX && answer;x++)
  206.         {
  207.         cnt=0;
  208.         for(y=0;y<BOARDY;y++)
  209.             if(joinmtrx[ELM(x,y)]) cnt++;
  210.  
  211.         if((cnt&1)==1) answer=0;
  212.         }
  213.  
  214.     return answer;
  215.     }
  216.  
  217. short comp_rules(struct board *board,short p1,short p2)
  218.     {
  219.     short way,c1,c2;
  220.  
  221.     c1=board->solution[p1]->solname-1;
  222.     c2=board->solution[p2]->solname-1;
  223.  
  224.     way=rulecombo[c1][c2];
  225.  
  226.     if(way&9)
  227.         {
  228.         board->rule[0]++;
  229.         if(overlap(board,p1,p2)) return NO;
  230.         }
  231.  
  232.     if(way&2)
  233.         {
  234.         board->rule[1]++;
  235.         if(claimeven_below(board,p1,p2)) return NO;
  236.         }
  237.  
  238.     if(way&4)
  239.         {
  240.         board->rule[2]++;
  241.         if(!column_wdoe(board,p1,p2)) return NO;
  242.         }
  243.  
  244.     return YES;
  245.     }
  246.  
  247. void build_adjacency_matrix(char **matrix,struct board *board)
  248.     {
  249.     short x,y;
  250.  
  251.     for(x=0;x<board->sp;x++)
  252.         for(y=x;y<board->sp;y++)
  253.             {
  254.             if(x==y) matrix[x][x]=NO;
  255.             else if(comp_rules(board,x,y)) matrix[y][x]=YES;
  256.             else matrix[y][x]=NO;
  257.             }
  258.     }
  259.  
  260. void dump_no_adjacencies(char **matrix,struct board *board)
  261.     {
  262.     long comp=0,uncomp=0;
  263.     short x,y,px1,px2,py1,py2,i;
  264.  
  265.     printf("Adjacency matrix faults\n\r");
  266.  
  267.     for(x=0;x<board->sp-1;x++)
  268.         for(y=x+1;y<board->sp;y++)
  269.             {
  270.             if(matrix[y][x]==NO)
  271.                 {
  272.                 uncomp++;
  273.                 px1=ELX(board->solution[x]->solpoint[0]);
  274.                 py1=ELY(board->solution[x]->solpoint[0]);
  275.                 px2=ELX(board->solution[x]->solpoint[1]);
  276.                 py2=ELY(board->solution[x]->solpoint[1]);
  277.  
  278.                 printf("%13s ",rulename[board->solution[x]->solname-1]);
  279.                 printf("%c%d-%c%d  ",px1+97,py1+1,px2+97,py2+1);
  280.  
  281.                 for(i=0;i<6;i++)
  282.                     {
  283.                     if(i<board->solution[x]->sqinvnumb)
  284.                         printf("%2d,",board->solution[x]->sqinv[i]);
  285.                     else printf("   ");
  286.                     }
  287.  
  288.                 px1=ELX(board->solution[y]->solpoint[0]);
  289.                 py1=ELY(board->solution[y]->solpoint[0]);
  290.                 px2=ELX(board->solution[y]->solpoint[1]);
  291.                 py2=ELY(board->solution[y]->solpoint[1]);
  292.  
  293.                 printf("%13s ",rulename[board->solution[y]->solname-1]);
  294.                 printf("%c%d-%c%d  ",px1+97,py1+1,px2+97,py2+1);
  295.  
  296.                 for(i=0;i<6;i++)
  297.                     {
  298.                     if(i<board->solution[y]->sqinvnumb)
  299.                         printf("%2d,",board->solution[y]->sqinv[i]);
  300.                     else printf("   ");
  301.                     }
  302.  
  303.                 printf("\n\r");
  304.                 }
  305.             else comp++;
  306.             }
  307.  
  308.     printf("\n\r");
  309.     printf("Total rules %d, matrix size %ld bytes\n\r",board->sp,(long)board->sp*board->sp);
  310.     printf("Comb. rules uncomp=%ld, comp=%ld, total=%ld\n\r",uncomp,comp,uncomp+comp);
  311.     }
  312.